package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。
 *      返回这一子串的长度。
 *
 * 2. 算法分析
 *      1. 暴力法 枚举字符串中出现的所有子串区间  时间复杂度为O(n^3) 超时时间限制
 *
 *      2. 优化暴力法  前缀和+暴力
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q027_至少有K个重复字符的最长子串 {

    /**
     * 暴力法
     * @param s
     * @param k
     * @return
     */
    public int longestSubstring1(String s, int k) {
        char[] charArrayS = s.toCharArray();
        int n = charArrayS.length;
        int maxLen = 0; // 记录全局最长满足题意的字符串的长度
        for(int i = 0; i < n; i++) { // 扫描起始位置
            for(int j = i; j < n; j++) { // 扫描结束位置
                // 判断当前[i,j]字串是否满足条件
                int[] freq = new int[26];
                for(int t = i; t <= j; t++) {
                    freq[charArrayS[t] - 'a']++;
                }
                boolean isStatisfied = true;
                for(int t = i; t <= j; t++) {
                    if(freq[charArrayS[t] - 'a'] < k) {
                        isStatisfied = false;
                        break;
                    }
                }
                if(isStatisfied == true && maxLen < j - i + 1) {
                    maxLen = j - i + 1;
                }
            }
        }
        return maxLen;
    }

    /**
     * 优化之后的暴力法   前缀和 + 暴力   没有超出时间限制，但是效率非常低
     * @param s
     * @param k
     * @return
     */
    public int longestSubstring2(String s, int k) {
        char[] charArrayS = s.toCharArray();
        int n = charArrayS.length;
        int maxLen = 0; // 记录全局最长满足题意的字符串的长度
        // 这个前缀和数组的含义 prefix[i][26] 前i个字符每个字符出现的次数记录在一个长度为26的int数组中
        int[][] prefix = new int[n+1][26];
        // 初始化前缀和数组
        // 由于上述给出的前缀和的含义，如果我们想要统计前i个字符每个字符出现的次数
        // 我们只需要拷贝前i-1个字符出现的次数的int数组，然后更新当前字符的次数
        for(int i = 1; i < n + 1; i++) {
            for(int j = 0; j < 26; j++) {
                prefix[i][j] = prefix[i-1][j]; // 拷贝上一层的
            }
            prefix[i][charArrayS[i-1] - 'a']++;
        }

        // 得到前缀和数组之后我们该如何求出[i,j)字串中每个字符出现的次数呢?
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j <= n; j++) {
                // 考虑当前区间[i,j)是否满足条件
                int[] freq = new int[26];
                boolean isStatisifed = true; // 布尔判断当前是否满足的变量
                for(int l = 0; l < 26; l++) {
                    freq[l] = prefix[j][l] - prefix[i][l];
                    if(freq[l] > 0 && freq[l] < k) {
                        // 当前字符出现了，但是次数小于k，没有出现的字符不考虑
                        isStatisifed = false;
                    }
                }
                if(isStatisifed) {
                    maxLen = Math.max(maxLen,j - i);
                }
            }
        }
        return maxLen;
    }

    /**
     * 分治算法实现
     * @param s
     * @param k
     * @return
     */
    public int longestSubstring3(String s, int k) {
        return -1;
    }
}
